//
// Description: 120. 三角形最小路径和
// Created by Loading on 2022/7/3.
//

#include <bits/stdc++.h>

using namespace std;

int minimumTotal(vector<vector<int>> &triangle) {
    int n = triangle.size();

    // 减少空间复杂度，使用滚动数组
    vector<int> dp(n, 1e9);
    dp[0] = triangle[0][0];

    for (int i = 1; i < n; ++i) {
        // 逆序遍历
        for (int j = i; j >= 0; --j) {
            if (j != 0) {
                dp[j] = min(dp[j - 1], dp[j]);
            }
            dp[j] += triangle[i][j];
        }
    }

    return *min_element(dp.begin(), dp.end());
}

int main() {
    vector<vector<int>> triangle{{2},
                                 {3, 4},
                                 {6, 5, 7},
                                 {4, 1, 8, 3}};

    int res = minimumTotal(triangle);

    cout << res << endl;

    return 0;
}
